import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.Vector;
import src.FileParser;
import src.FileWriter;
import src.Ronda;


public class Tp_Ej2_Main {
	
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		String nombreArchivo = "Tp1";
		
		String archivoEntrada = ".\\resources\\" + nombreArchivo + "Ej2.in";
		String archivoSalida = ".\\resources\\" + nombreArchivo + "Ej2.out";
		String archivoTiempos = ".\\resources\\" + nombreArchivo + "Ej2.time";
		
		//crearPeorCaso(archivoEntrada);
		//crearMejorCaso(archivoEntrada);
		algoritmo(archivoEntrada, archivoSalida, archivoTiempos);
	}
	
	private static void algoritmo(String archivoEntrada, String archivoSalida, String archivoTiempos){
		FileParser fp = new FileParser(archivoEntrada);
		FileWriter fw = new FileWriter(archivoSalida);
		FileWriter fwTiempos = new FileWriter(archivoTiempos);
		int cantidadRepeticiones=5;
		long minMedicion=0;
		boolean res = true;
		
		while (!fp.getLine().trim().equals("-1")){
			Ronda instancia = parsearInstancia(fp);
			
			for (int rep=0 ;rep<cantidadRepeticiones;rep++) {
				long tiempoInicio = System.nanoTime();
				res = seCumpleRonda(instancia);
				long totalTiempo = System.nanoTime()- tiempoInicio;
				minMedicion+=totalTiempo;
			}
			minMedicion /= cantidadRepeticiones;
			fwTiempos.writeLine(instancia.getCantAmigos() + " " + String.valueOf(minMedicion));
			
			System.out.println("El resultado de la instancia es: " + res);
			if (res)
				fw.writeLine("ronda");
			else
				fw.writeLine("no");
		}
		
		fp.closeFile();
		fw.closeFile();
		fwTiempos.closeFile();
	}
	
	private static void crearMejorCaso(String archivoEntrada){
		FileWriter fw = new FileWriter(archivoEntrada);
		Ronda r = new Ronda();
		
		for (int cant=10;cant<=100;cant++){
			r.setCantAmigos(cant);
			
			for (int i=1;i<=cant;i++){
				Vector<Integer> relacion = new Vector<Integer>();
				for (int j=1; j<=cant;j++){
					if (i != j){
						if ((i == 1 && j == 2) || (i == 2 && j == 1)){
							
						}else
							relacion.add(j);
					}
				}
				r.agregarRelacion(i,relacion);
			}
			fw.writeLine(String.valueOf(r.getCantAmigos()));
			fw.writeRonda(r);			
		}
		fw.writeLine("-1");
		fw.closeFile();
	}
	
	private static void crearPeorCaso(String archivoEntrada){
		FileWriter fw = new FileWriter(archivoEntrada);
		Ronda r = new Ronda();
		//Cantidad tiene que ser mayor o igual que 4.
		for(int cant =10;cant<101;cant++){
			r.setCantAmigos(cant);
			
			for (int i=1;i<=cant;i++){
				Vector<Integer> relacion = new Vector<Integer>();
				if (i == 1 || i == 3){
					relacion.add(2);
					relacion.add(4);
				} else
				{	
					for (int j=1; j<=cant;j++){
						if (i != j){
							if (i == 2 && j == 4){
								
							}else
							if (i == 4 && j == 2){
								
							}else
								relacion.add(j);
						}
					}
				}
				r.agregarRelacion(i,relacion);
			}
			fw.writeLine(String.valueOf(r.getCantAmigos()));
			fw.writeRonda(r);
		}
		fw.writeLine("-1");
		fw.closeFile();
	}
	
	private static Ronda parsearInstancia(FileParser fp){
		Ronda r = new Ronda();
		String[] str = fp.getLine().trim().replaceAll("\\s+", " ").split("\\s");
		r.setCantAmigos(Integer.parseInt(str[0]));
		Integer id = 1;
		fp.nextLine();
		
		while (id <= r.getCantAmigos()){
			String[] str2 = fp.getLine().trim().replaceAll("\\s+", " ").split("\\s");
			Vector<Integer> res = new Vector<Integer>();
			int cantAmigosActual = Integer.parseInt(str2[0]);
			int i = 1;
			
			while (i <= cantAmigosActual){
				res.add(Integer.parseInt(str2[i]));
				i++;
			}
			
			r.agregarRelacion(id, res);
			fp.nextLine();
			id++;
		}
		
		return r;
	}
	
	private static boolean seCumpleRonda(Ronda r) {
		
		if (haySuficientes(r))
			return true;
		
		if (hayMuyPocos(r))
			return false;
		
		return hayRonda(r, new ArrayList<Integer>(), Ronda.PRIMERO);
	}
	
	private static boolean haySuficientes(Ronda r) {
		return (cantidadRelaciones(r) >= cantidadMaximaRelaciones(r));
	}
	
	private static int cantidadMaximaRelaciones(Ronda r) {
		int res = r.getCantAmigos();
		res *= (res - 1);
		res /= 2;
		return res;
	}
	
	private static int cantidadRelaciones(Ronda r) {
		int i = 1;
		int res = 0;
		
		while (i <= r.getCantAmigos()){
			res += r.getRelaciones().get(i).size(); 
			i++;
		}
		
		res/= 2;
		return res;
	}
	
	private static boolean hayMuyPocos(Ronda r) {
		int i = 1;
		boolean res = false;
		
		while (i <= r.getCantAmigos() && !res){
			res = (r.getRelaciones().get(i).size() < 2); 
			i++;
		}
		
		return res;
	}
	
	private static boolean hayRonda(Ronda r, List<Integer> visitados, int ultimo) {
		visitados.add(ultimo);
		if (visitados.size() == r.getCantAmigos())
			return esAmigoDe(r, Ronda.PRIMERO, ultimo);
		else {
			Vector<Integer> amigos = r.getRelaciones().get(ultimo);
			Iterator<Integer> it = amigos.iterator();
			while ( it.hasNext() ) {
				int amigo = it.next();
				if (!visitados.contains(amigo)){
					if (hayRonda(r, visitados, amigo))
						return true;
				}
			}
		}
		visitados.remove(visitados.size()-1);
		
		return false;
	}
	
	private static boolean esAmigoDe(Ronda r, int primero, int ultimo) {
		return r.getRelaciones().get(primero).contains(ultimo);
	}
	
}
